/**
 * 给定一个带权树（0-index,0-root），再给定Q个询问，对每一个询问(u, v)，求：
 * 求从u到v路径上的一个点x，使得u到x的距离大于等于u到v距离的一半，且x是距离u最近的
 * 显然需要求lca，因此令Pij为i的2的j次方级祖先，先求出P
 * Pi0即i的直接父节点。再令Di为根到i节点的距离。
 * 一次dfs可以求出P、D。再求P的时候顺便需要求出深度Depth。
 * 
 * 对每一次询问u/v，首先求出u、v的lca，再根据D[lca]、D[u]、D[v]
 * 可知路径长度以及lca分别到u、v的距离，于是可知答案是在u到lca段还是v到lca段
 * 
 * 令 proc(u, w) 为从u往上走不超过w距离所能到达的最远节点，记作x
 * 即u到x的距离最大为w，而u到P[x][0]的距离必然大于w
 * 
 * 则假设答案在u到lca段，只需求出 P[proc(u, half-1)][0] 即可。
 * 其中half = (duv + 1) / 2
 * 即从u到x最多为half-1，恰好还没有到一半，再到x的直接父节点即是答案
 * 
 * 如果答案在v到lca段，只需求出 proc(v, duv - half)即可
 * 即v到x的距离最多是duv-half，则u到x的距离至少half，因此x是答案
 * 
 * proc(u, w)可以使用递归完成
 * 令proc_iter(u, k, w)求出从u开始向上k级不超过w的最远节点
 * proc_iter(u, k, w):
 *     if k < 0: return u
 *     令 p = Parent[u][k]
 *     令 d = D[u] - D[p]
 *     if d > w: return proc_iter(u, k - 1, w) # 说明k级大了，调小一级
 *     return proc_iter(p, k - 1, w - d) # 说明d距离可以用掉，现在把新的起点定为p，级别为k-1，可否为k-2?
 */
class Solution {

using llt = long long;

struct edge_t{
    int from;
    int to;
    llt w;
};

int N;
vector<vector<edge_t>> G;

vector<int> Log2;
vector<int> Depth;
vector<vector<int>> Parent;
vector<llt> D;

public:
    vector<int> findMedian(int N, vector<vector<int>>& edges, vector<vector<int>>& queries) {
        this->N = N;
        G.assign(N + 1, {});
        for(const auto & v : edges){
            int a = v[0] + 1, b = v[1] + 1, c = v[2];
            G[a].push_back({a, b, c});
            G[b].push_back({b, a, c});
        }    

        Log2.assign(N + 1, 0);
        //初始化
        for(int i=1;i<=N;++i){
            Log2[i] = Log2[i-1] + ((1 << Log2[i-1])==i?1:0);
        }	

        D.assign(N + 1, 0LL);
        Depth.assign(N + 1, 0);
        Parent.assign(N + 1, vector<int>(Log2[N] + 1, 0));
        this->dfs(1, 0, 0);

        vector<int> ans;
        ans.reserve(queries.size());
        for(const auto & vec : queries){
            int a = vec[0] + 1, b = vec[1] + 1;
            ans.emplace_back(proc(a, b));  
        }
        return ans;
    }
    void dfs(int u, int p, llt w){
        Parent[u][0] = p;
        D[u] = D[p] + w;
        Depth[u] = Depth[p] + 1;
        //确定u的各级祖先
        for(int i=1,n=Log2[Depth[u]];i<=n;++i){
            Parent[u][i] = Parent[Parent[u][i-1]][i-1];
        }
        for(const auto & e : G[u]){
            if(e.to == p) continue;
            dfs(e.to, u, e.w);
        }
        return;
    }
    int lca(int x, int y){
        if(Depth[x]<Depth[y]) swap(x,y);
        //把x和y调整到一个深度区间内
        while(Depth[x]>Depth[y]) x = Parent[x][Log2[Depth[x]-Depth[y]]-1];
        if(x==y) return x;
        //一起往上跳
        for(int k=Log2[Depth[x]]-1;k>=0;--k){
            if(Parent[x][k]!=Parent[y][k]){
                x = Parent[x][k];
                y = Parent[y][k];
            }
        }
        return Parent[x][0];
    }
    int proc(int a, int b){
        // 特判
        if(a == b) return a - 1;
        int father = this->lca(a, b);
        auto dfather = D[father];
        auto duv = D[a] + D[b] - dfather - dfather;
        auto dfa = D[a] - dfather;
        auto half = (duv + 1) >> 1;
        int ans = -1;
        if(dfa >= half){ // 说明要去 u->lca 找
            ans = this->proc(a, half - 1); 
            ans = this->Parent[ans][0];       
        }else{ // 说明要去 v->lca 找
            ans = this->proc(b, duv - half);
        }
        return ans - 1;
    }
    // 从u往上走最多w的距离，令返回为r
    // 则u->r的距离最多为w，u->r->parent的距离必然超过w
    int proc(int u, llt w){
        // 注意要减去根的深度，也就是减一
        int k = Log2[Depth[u] - Depth[1]] - 1;
        return this->proc_iter(u, k, w);
    }
    int proc_iter(int u, int k, llt w){
        if(k < 0) return u;

        int p = Parent[u][k];
        auto d = D[u] - D[p];
        if(d > w) return this->proc_iter(u, k - 1, w);
        return this->proc_iter(p, k - 1, w - d);
    }
};
